#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>

void display(int *array,int n,int *indexX,int *indexY,int rank,int size,int k){
	MPI_Status status;	
	int i;
	int *new = malloc(sizeof(int)*n);
	if(rank != 0)		
		MPI_Send(&array[indexX[rank]],indexY[rank]-indexX[rank]+1,MPI_INT,0,0,MPI_COMM_WORLD);
	else
		for(i = 1;i < size;i++)
			MPI_Recv(&new[indexX[i]],indexY[i]-indexX[i]+1,MPI_INT,i,MPI_ANY_TAG,MPI_COMM_WORLD,&status);
	if(rank == 0){
		for(i = 0;i <= indexY[0];i++)
			new[i] = array[i];
		for(i = 0;i < n;i++)
			printf("%d ",new[i]);				
		printf("\n");
	}
}

int main(int argc, char **argv){
	int size,rank;
	FILE* in = fopen("in.txt","r");
	int i,n,k;
	int *array;
	fscanf(in,"%d",&n);
	array = malloc(sizeof(int)*n);
	for(i = 0;i < n;i++)
		fscanf(in,"%d",&array[i]);	
	MPI_Init(&argc, &argv);
	MPI_Status status;
	MPI_Comm_size(MPI_COMM_WORLD, &size);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);

	int *indexX = malloc(sizeof(int)*size);
	int *indexY = malloc(sizeof(int)*size);
	int *stop = malloc(sizeof(int)*size);
	for(i = 0;i < size;i++){
		indexX[i] = (n/size*i)/2*2;
		stop[i] = 0;
	}
	for(i = 0;i < size-1;i++)
		indexY[i] = indexX[i+1]-1;
	indexY[size-1] = n-1;

	k = 0;
	double time0,time1,time2,time3,alltime1,alltime2;
	time0 = MPI_Wtime();
	while(1){		
		if(k%2 == 1){
			time1 = MPI_Wtime();
			if(rank < size-1)			
				MPI_Recv(&array[indexY[rank]+1],1,MPI_INT,rank+1,k,MPI_COMM_WORLD,&status);
			if(rank > 0)
				MPI_Send(&array[indexX[rank]],1,MPI_INT,rank-1,k,MPI_COMM_WORLD);
			time2 = MPI_Wtime();
			alltime1 += time2-time1;
		}
		stop[rank] = 0;
		int index;
		if(rank < size-1)
			index = indexY[rank]+1;
		else
			index = indexY[rank];
		for(i = k%2+indexX[rank];i <= index;i+=2){
			if(i < n-1 && array[i] > array[i+1]){
				int t = array[i];
				array[i] = array[i+1];
				array[i+1] = t;
				stop[rank] = 1;
			}
		}
		if(k%2 == 1){
			time1 = MPI_Wtime();
			if(rank < size-1)			
				MPI_Send(&array[indexY[rank]+1],1,MPI_INT,rank+1,k,MPI_COMM_WORLD);
			if(rank > 0)
				MPI_Recv(&array[indexX[rank]],1,MPI_INT,rank-1,k,MPI_COMM_WORLD,&status);
			time2 = MPI_Wtime();
			alltime1 += time2-time1;
		}
		int Finalize = 1;
		time1 = MPI_Wtime();
		if(rank != 0)
			MPI_Send(&stop[rank],1, MPI_INT,0,k,MPI_COMM_WORLD);
		else{
			for(i = 1;i < size;i++)
				MPI_Recv(&stop[i],1,MPI_INT,i,k,MPI_COMM_WORLD,&status);
			for(i = 0;i < size;i++)
				if(stop[i] == 1)
					Finalize = 0;
		}
		if(rank != 0)
			MPI_Recv(&Finalize,1,MPI_INT,0,k,MPI_COMM_WORLD,&status);
		else
			for(i = 1;i < size;i++)
				MPI_Send(&Finalize,1,MPI_INT,i,k,MPI_COMM_WORLD);
		time2 = MPI_Wtime();
		alltime1 += time2-time1;
		if(Finalize == 1){
			time3 = MPI_Wtime();
			alltime2 = time3-time0;
			printf("%lf\n",alltime1/alltime2);			
			//display(array,n,indexX,indexY,rank,size,k);
			MPI_Finalize();
			break;
		}
		time1 = MPI_Wtime();
		MPI_Barrier(MPI_COMM_WORLD);
		time2 = MPI_Wtime();
		alltime1 += time2-time1;
		k++;		
	}
	return 0;	
}
